//#include"clist.h"
#include<malloc.h>
#include<assert.h>
#include<stdio.h>

//头插 尾插 按值删


//注意：循环链表的for循环中不可以出现NULL,

//void InitList(CList plist);
//
////头插
//bool Insert_head(CList plist, int val);
//
////尾插
//bool Insert_tail(CList plist, int val);
//
////插入数据，在plist链表的pos位置插入val;
//bool Insert(CList plist, int pos, int val);
//
////判空
//bool IsEmpty(CList plist);
//
////获取数据节点的个数
//int GetLength(CList plist);
//
////在plist中查找第一个key值，找到返回节点地址，没有找到返回NULL；
//CNode* Search(CList plist, int key);
//
////删除pos位置的值
//bool DelPos(CList plist, int pos);
//
////删除第一个val的值
//bool DelVal(CList plist, int val);
//
////返回key的前驱地址，如果不存在返回NULL；
//CNode* GetPrio(CList plist, int key);
//
////返回key的后继地址，如果不存在返回NULL；
//CNode* GetNext(CList plist, int key);
//
////输出
//void Show(CList plist);
//
////清空数据
//void Clear(CList plist);
//
////销毁整个内存
//void Destroy(CList plist);

//循环链表
typedef struct CNode 
{
	int data;
	struct CNode* next;//后继节点指针

	//这个指针：指向的就带一个数据域和地址

}CNode, * CList;
//CNode*=CList



//初始化
void InitList(CList plist)
{
	assert(plist != NULL);
	if (plist == NULL)
		return;

	//头节点的数据域不使用
	plist->next = plist;//环形
}
//返回key的前驱地址，如果不存在返回NULL；
CNode* GetPrio(CList plist, int key)
{
	CNode* p;
	for (p = plist; p->next != plist; p = p->next)
	{
		if (p->next->data == key)
		{

			return p;
		}
	}
	return NULL;

}


//头插
bool Insert_head(CList plist, int val)
{
	assert(plist != NULL);
	if (plist == NULL)
		return false;

	//申请节点
	CNode* p = (CNode*)malloc(sizeof(CNode));
	assert(p != NULL);
	//放入数据
	p->data = val;
	//头插
	p->next = plist->next;
	plist->next = p;
	return true;

}

//尾插
bool Insert_tail(CList plist, int val)
{
	assert(plist != NULL);
	if (plist == NULL)
		return false;

	//创建新节点
	CNode* p = (CNode*)malloc(sizeof(CNode));
	assert(p != NULL);
	p->data = val;
	//找尾巴
	CNode* q;
	for (q = plist; q->next != plist; q = q->next)
	{
		;
	}
	//尾插
	p->next = q->next;//p->next=plist;
	q->next = p;

	return true;
}
//获取数据节点的个数
int GetLength(CList plist)
{
	assert(plist != NULL);
	if (plist == NULL)
		return 0;
	int count = 0;
	for (CNode* p = plist->next; p != plist; p = p->next)
	{
		count++;
	}
	return count;
}


//插入数据，在plist链表的pos位置插入val;
bool Insert(CList plist, int pos, int val)
{
	if (pos<0 || pos>GetLength(plist))
	{
		return false;
	}
	//申请节点
	CNode* p = (CNode*)malloc(sizeof(CNode));
	assert(p != NULL);
	p->data = val;
	//找位置
	/*CNode* q;
	int i = 0;
	for (q = plist;i < pos;i++, q = q->next)
	{
		;
	}*/
	CNode* q = plist;
	int i = 0;
	while (i < pos)
	{
		i++;
		q = q->next;
	}


	//插入
	p->next = q->next;
	q->next = p;

	return true;
}

//判空
bool IsEmpty(CList plist)
{
	return plist->next == plist;
}


//在plist中查找第一个key值，找到返回节点地址，没有找到返回NULL；
CNode* Search(CList plist, int key)
{
	assert(plist != NULL);
	if (plist == NULL)
		return NULL;
	for (CNode* p = plist->next; p != plist; p = p->next)
	{
		if (p->data == key)
		{
			return p;
		}
	}
	return NULL;
}

//删除pos位置的值
bool DelPos(CList plist, int pos)
{
	if (pos < 0 || pos >= GetLength(plist))
	{
		return false;
	}
	CNode* p;
	int i;
	for (p = plist, i = 0; i < pos; i++, p = p->next)
	{
		;
	}
	CNode* q = p->next;//q是要删除的点

	p->next = q->next;
	free(q);

	return true;

}


bool DelVal(CList plist, int val)
{
	CNode* p = GetPrio(plist, val);
	if (p == NULL)
	{
		return false;
	}
	//删除的三句话：1.先保存 2.穿透着删除 3.最后free
	CNode* q = p->next;//q为要删除的点
	p->next = q->next;
	free(q);

	return true;
}



//返回key的后继地址，如果不存在返回NULL；
CNode* GetNext(CList plist, int key)
{
	CNode* p = Search(plist, key);
	if (p == NULL)
		return NULL;
	return p->next;
}

//输出
void Show(CList plist)
{
	for (CNode* p = plist->next; p != plist; p = p->next)
	{
		printf("%d  ", p->data);
	}
	printf("\n");
}
//销毁整个内存
void Destroy(CList plist)
{
	//总是删除第一个数据节点
	CNode* p;
	while (plist->next != plist)
	{
		p = plist->next;
		plist->next = p->next;
		free(p);
	}
}
//清空数据
void Clear(CList plist)
{
	Destroy(plist);
}




//Clist测试
//int main()
//{
//	CNode c;
//	InitList(&c);
//	for (int i = 0;i < 10;i++)
//	{
//		Insert(&c, i, i);
//	}//0 1 2 3 4 5 6 7 8 9
//	Show(&c);
//	//头插
//	Insert_head(&c, 1);
//	Show(&c);//1 0 1 2 3 4 5 6 7 8 9
//
//	//尾插
//	Insert_tail(&c, 3);
//	Show(&c);//1 0 1 2 3 4 5 6 7 8 9 3
//
//	//按位置删除（没说就是从0号位置开始删除）
//	DelPos(&c, 1);
//	Show(&c);////1 1 2 3 4 5 5 7 8 9 3
//
//	//按值删除
//	DelVal(&c, 0);//1 1 2 3 4 5 5 7 8 9 3
//	Show(&c);
//	return 0;
//}